/*
 * @(#)IntegerFactoringPollardRho.java                  0.1 2011-11-09
 * 
 * Copyright (c) 2011 David Falk, Klaus Nicosia, Marcus Oberg.
 */

import java.math.BigInteger;
import java.util.LinkedList;
import java.util.Random;

/**
 * Application that tries to factor 100 numbers with Pollard-Rho.
 * 
 * @author      David Falk
 * @author      Klaus Nicosia
 * @author      Marcus Oberg.
 */
public class IntegerFactoring {

	/** Number of numbers to factor. */
	private static final int NUMBERS = 100;

	/** Instance of the factoring algorithm. */
	private static IntegerFactoringPollardRho pollardFactoring =
		new IntegerFactoringPollardRho();

	/** Input and output streams. */
	private static Kattio io;

	/** Sensitivity for prime testing. */
	private static final int PRIME_SENS = 10;

	/**
	 * Linked list to store the factors of the current number, until all
	 * factors are found and they are ready to be printed. Discarded if giving
	 * up.
	 */
	private static LinkedList<String> factors = new LinkedList<String>();

	/** Start time for this execution. */
	private static long startTime;

	/** Current "time". */
	private static long time;

	/** Time limit for this run (all numbers). */
	private static final long TIME_LIMIT = (long) (14.5 * Math.pow(10, 9));

	/**
	 * Runs Pollard's Rho heuristic with Bernt's cycle detection algorithm and
	 * optimization for the number of GCD calculations.
	 * 
	 * @param args
	 */
	public static void main(String[] args) {
		startTime = System.nanoTime();
		IntegerFactoring factoring = new IntegerFactoring();
		io = new Kattio(System.in, System.out);

		factoring.runKattis();
//		factoring.runOffline(100);
	}

	/**
	 * For testing purposes.
	 * 
	 * Runs the factoring algorithm on 100 b-bit numbers.
	 * 
	 * @param       b       number of bits in the random numbers.
	 */
	private void runOffline(int b) {
		BigInteger n;
		int failed = 0;
		Random random = new Random();

		for (int i = 0; i < 100; i++) {
			n = new BigInteger(b, random);
			System.out.println("i: " + i + ", n: " + n + " (Bits: "
					+ n.bitLength() + ", Digits: " + n.toString().length()
					+ ")");
			factorInteger(n);
			if (time - startTime > TIME_LIMIT) {
				factors = new LinkedList<String>();
				n = BigInteger.ONE;
				i = failRestOffline(i);
			}
			if (factors.isEmpty()) {
				io.println("fail");
				failed++;
			} else {
				for (String s : factors) {
					io.println(s);
				}
				factors = new LinkedList<String>();
			}
			io.println();
			io.flush();
			time = System.nanoTime();
		}
		double finishTime = ((time - startTime) * Math.pow(10, -9));
		io.println("Failed: " + failed + " (" +  finishTime  + " s).");
		io.close();
	}

	/**
	 * Runs the factoring algorithm on KATTIS and reads the (100) numbers from
	 * standard input.
	 */
	public void runKattis() {
		BigInteger n;

		while (io.hasMoreTokens()) {
			n = new BigInteger(io.getWord());

			if (n.bitLength() > 100) {
				io.println("fail");
			} else {
				factorInteger(n);
				if (time - startTime > TIME_LIMIT) {
					factors = new LinkedList<String>();
					n = BigInteger.ONE;
					failRest();
				}
				if (factors.isEmpty()) {
					io.println("fail");
				} else {
					for (String s : factors) {
						io.println(s);
					}
				}
				factors = new LinkedList<String>();
			}
			io.println();
		}
		io.close();
	}

	/**
	 * Runs the factoring algorithm on n to generate a factor and then
	 * recursively runs the algorithm on factor and n / factor.
	 * Adds every factor to the LinkedList factors, the list is emptied on
	 * failure.
	 * 
	 * @param       n       the number n to factor into primes.
	 * @return              returns 1 when done or failed.
	 */
	public void factorInteger(BigInteger n) {
		BigInteger factor;

		if (n.isProbablePrime(PRIME_SENS)) { // Prime factor found.
			factors.add(n.toString());
		} else { // Composite found or algorithm failed.
			factor = pollardFactoring.pollardBrent(n);

			if (factor.compareTo(BigInteger.ONE.negate()) == 0) { // Fail.
				factors = new LinkedList<String>();
			} else {
				factorInteger(factor); // Factor the composite factor.
				if (!factors.isEmpty()) {
					factorInteger(n.divide(factor)); // Factor n / factor.
				}
			}
		}
	}

	/**
	 * Prints the rest of the numbers as failures.
	 * 
	 * @param       i       current number.
	 * @return              returns the number of numbers done.
	 */
	public int failRestOffline(int i) {
		while(i < NUMBERS - 1) {
			io.println("fail");
			io.println();
			io.flush();
			i++;
			System.out.println("i: " + i);
		}
		return i;
	}

	/**
	 * Prints the rest of the numbers as failures.
	 */
	public void failRest() {
		while(io.hasMoreTokens()) {
			io.println("fail");
			io.println();
			io.getWord();
		}
	}

	/** Set current "time". */
	public static void setTime(long t) {
		time = t;
	}

	/** Get current "time". */
	public static long getTime() {
		return time;
	}

	/** Get time for start of execution, */
	public static long getStartTime() {
		return startTime;
	}

	/** Get time limit for this execution. */
	public static long getTimeLimit() {
		return TIME_LIMIT;
	}
}